package Tree.TrieTree;


/*
    字典树
    根不存字母，存'/'
    字典树，顾名思义，就是把字典构成一棵树，里面节点的字母按照字典序排列
    一个节点有26个孩子指针，分别对应26个字母
    在字典树中最频繁的两个操作就是：
    ① 把一个单词插入树中
    ② 查找一个单词是否存在

    对于精确查询，红黑树和哈希表更加合适，而且Java中有对应的实现，不需要自己手写
    字典树更加适合模糊查询，但是要手动从0构建代码
 */
public class Trie {
    private TrieNode root = new TrieNode('/');

    //操作①
    public void insert(char[] text) {
        TrieNode p = root;
        for (int i = 0; i < text.length; i++) {
            //找到下一个字母应该存的位置
            int index = text[i] - 'a';
            if (p.children[index] == null) {
                TrieNode newNode = new TrieNode(text[i]);
                p.children[index] = newNode;
            }
            p = p.children[index];
        }
        //isEndingChar为true的话说明到此为止是一个完整的单词
        //比如safe和safety，分别在e和y处，isEndingChar要设置为true
        p.isEndingChar = true;
    }

    //操作②
    public boolean find(char[] pattern) {
        TrieNode p = root;
        for (int i = 0; i < pattern.length; i++) {
            int index = pattern[i] - 'a';
            //如果单词没到最后，但是发现字典空了，说明没找到，返回false
            if (p.children == null) {
                return false;
            }
            p = p.children[index];
        }
        //isEndingChar为false，说明单词未结束，但是按道理应该要结束了
        //说明要找的单词pattern是当前找到的单词的前缀
        //举个例子：要找safe，树中只有safety，匹配到e的时候，pattern结束了
        //却发现e不是单词的末尾（isEndingChar为false），所以还是属于没有找到的情况
        if (p.isEndingChar == false) return false;
        else return true;
    }
}

class TrieNode {
    public char data;
    public TrieNode children[] = new TrieNode[26];
    public boolean isEndingChar = false;

    public TrieNode(char data) {
        this.data = data;
    }
}